如何设计一个搜索提示系统？
在互联网增长速度趋于稳定的今天，许多大厂已将面试重心从八股文转向场景题，也就是系统设计，强调应聘者在实际工作环境中的解决问题能力。这就是我推出的系统设计系列的初衷，专注于系统设计的深度学习和面试技巧。在这个系列中，提供大量真实的系统设计场景题，以及高效的解决方案。无论您是初学者还是资深从业者，都能在这里得到宝贵的知识和经验。点击关注
我们来设计一个实时建议服务，该服务将在用户输入搜索文本时向他们推荐词汇。
类似服务：自动建议，输入提示搜索
难度：中等
1. 什么是输入提示建议？
输入提示建议使用户能够搜索已知的和经常搜索的词汇。当用户在搜索框中输入时，它会尝试预测用户已经输入的字符的查询，并给出一个完成查询的建议列表。输入提示建议帮助用户更好地阐述他们的搜索查询。这并不是关于加速搜索过程，而是关于引导用户并帮助他们构建搜索查询。
2. 系统的需求和目标
功能性需求：当用户输入他们的查询时，我们的服务应该建议前10个以用户已输入内容开头的词汇。
非功能性需求：建议应该实时出现。用户应该在200毫秒内看到建议。
3. 基本系统设计和算法
我们需要解决的问题是，我们有很多“字符串”需要以某种方式存储，以便用户可以使用任何前缀进行搜索。我们的服务将会根据给定的前缀建议下一个匹配的词。例如，如果我们的数据库包含以下词：cap, cat, captain, capital，用户输入了‘cap’，我们的系统应该建议‘cap’, ‘captain’和‘capital’。
由于我们需要以最小的延迟服务大量的查询，我们需要提出一种有效地存储数据的方案，以便可以快速查询。我们不能依赖于某个数据库来做这件事；我们需要在内存中以一种高效的数据结构存储我们的索引。
一种可以满足我们目的的最适合的数据结构是Trie（发音为“try”）。Trie是一种树状数据结构，用于存储短语，其中每个节点按顺序存储短语的一个字符。例如，如果我们需要在trie中存储‘cap, cat, caption, captain, capital’，它看起来像：
现在如果用户输入了‘cap’，我们的服务可以遍历trie到达节点‘P’，找到所有以这个前缀开始的词（例如，cap-tion, cap-ital等）。
我们可以合并只有一个分支的节点以节省存储空间。上述trie可以这样存储：
我们应该使用大小写不敏感的trie吗？为了简单性和搜索用例，让我们假设我们的数据是大小写不敏感的。
如何找到顶部的建议？现在我们可以找到给定前缀的所有词，我们如何知道我们应该建议的前10个词是什么呢？一个简单的解决方案可能是存储在每个节点终止的搜索的计数，例如，如果用户搜索了‘CAPTAIN’100次和‘CAPTION’500次，我们可以
将这个数字与词组的最后一个字符一起存储。所以现在如果用户输入了 ‘CAP’，我们知道前缀‘CAP’下最常被搜索的词是‘CAPTION’。因此，给定一个前缀，我们可以遍历其下的子树以找到最佳建议。
给定一个前缀，遍历其子树需要多长时间？考虑到我们需要索引的数据量，我们应该预期一个巨大的树。即使遍历一个子树也需要很长时间，例如，短语‘system design interview questions’就有30层深。由于我们的延迟要求非常严格，我们确实需要提高解决方案的效率。
我们是否可以在每个节点存储最佳建议？这肯定可以加速我们的搜索，但需要大量的额外存储。我们可以在每个节点存储前10个建议，我们可以返回给用户。我们必须承受存储容量的大幅增加，以达到所需的效率。
我们可以通过仅存储终端节点的引用而不是存储整个词组来优化我们的存储。要查找建议的词，我们需要使用终端节点的父引用回溯。我们还需要存储每个引用的频率，以跟踪最佳建议。
我们如何构建这个trie？我们可以有效地自下而上地构建我们的trie。每个父节点将递归调用所有的子节点来计算他们的最佳建议和他们的计数。父节点将结合所有子节点的最佳建议来确定他们的最佳建议。
如何更新trie？假设每天有五十亿次搜索，这将给我们每秒大约60K的查询。如果我们试图为每个查询更新我们的trie，这将是极其资源密集的，这也会妨碍我们的读请求。处理这个问题的一个解决方案可能是在一定的时间间隔后离线更新我们的trie。
随着新的查询进入，我们可以记录它们并跟踪它们的频率。我们可以记录每个查询，或者进行抽样并记录每1000个查询。例如，如果
我们不希望展示被搜索次数少于1000次的词汇，因此安全地记录每1000次搜索的词汇是可行的。
我们可以设置Map-Reduce (MR)体系，定期处理所有的日志数据，比如每小时处理一次。这些MR作业将计算过去一小时内所有被搜索词汇的频率。然后我们可以用这些新数据更新我们的Trie树。我们可以获取Trie树的当前快照，并用所有新的词汇及其频率更新它。我们应该在离线状态下执行这个操作，因为我们不希望更新Trie树的请求阻碍我们的读取查询。我们有两个选项：
1. 我们可以在每个服务器上复制一份Trie树，进行离线更新。一旦完成，我们就可以切换到新的Trie树，并丢弃旧的。
2. 另一种选项是我们可以为每个Trie服务器设置主从配置。我们可以在主服务器服务流量时更新从服务器。更新完成后，我们可以将从服务器变为新的主服务器。稍后我们可以更新旧的主服务器，然后它也可以开始服务流量。
我们如何更新自动补全建议的频率？由于我们在每个节点上都存储了自动补全建议的频率，我们也需要更新它们。我们可以只更新频率的差异，而不是重新计算所有搜索词汇。如果我们记录了最近10天内所有被搜索词汇的数量，我们需要减去不再包括的时间段的计数，并增加新包括的时间段的计数。我们可以根据每个词汇的指数移动平均(EMA)来增加和减少频率。在EMA中，我们给予最新的数据更高的权重。它也被称为指数加权移动平均。
在Trie树中插入新词汇后，我们会去到该短语的终端节点并增加其频率。由于我们在每个节点上都存储了前10个查询，有可能这个特定的搜索词汇跳入了其他节点的前10个查询中。所以，我们需要更新那些节点的前10个查询。我们需要从节点回溯到根节点。对于每个父节点，我们检查当前的查询是否是前10中的一部分。如果是，我们就更新相应的频率。如果不是，我们检查当前的查询频率是否足够高，以成为前10的一部分。如果是，我们插入这个新词汇并移除频率最低的词汇。
我们如何从Trie树中移除一个词汇？假设我们因为某种法律问题、恶意或者侵权等原因需要从Trie树中移除一个词汇。我们可以在定期更新时从Trie树中彻底移除这类词汇，同时，在每个服务器上我们可以添加一个过滤层，会在发送给用户之前移除任何这样的词汇。
什么是建议排名的不同标准？除了简单的计数，对于词汇排名，我们还要考虑其他因素，比如新鲜度、用户位置、语言、人口统计、个人历史等。
4. Trie树的永久存储
如何将Trie树存储在文件中，以便我们可以轻松重建Trie树 - 这将在机器重启时需要？我们可以定期对Trie树进行快照并将其存储在文件中。这将使我们能够在服务器出现问题时重建Trie树。在存储时，我们可以从根节点开始，逐级保存Trie树。对于每个节点，我们可以存储它包含的字符和它有多少子节点。在每个节点后面，我们应该放置所有的子节点。假设我们有以下Trie树：
如果我们按照上述方案将这个Trie树存储在一个文件中，我们将有：“C2,A2,R1,T,P,O1,D”。从这里，我们可以轻松地重建我们的Trie树。
如果你注意到，我们并没有在每个节点上存储最佳建议和它们的数量。存储这些信息很困难；因为我们的Trie树是从上到下存储的，我们在父节点之前没有创建子节点，所以没有简单的方法可以存储他们的引用。为此，我们必须重新计算所有的最高频率词汇和计数。这可以在我们构建Trie树的时候完成。每个节点将计算其最佳建议并将其传递给其父节点。每个父节点将合并来自其所有子节点的结果，以找出其最佳建议。
5. 估算规模
如果我们正在构建一个与Google规模相当的服务，我们可以预计每天会有50亿次搜索，这将为我们提供大约每秒60K的查询。
由于在50亿的查询中会有很多重复的，我们可以假设只有20%的查询是独一无二的。如果我们只想对最高50%的搜索词汇进行索引，我们可以剔除大量的低频率搜索查询。假设我们将有1亿个独特的词汇，我们希望为其建立索引。
存储估计：如果平均每个查询包含3个词，且一个词的平均长度是5个字符，那么这将给我们15个字符的平均查询大小。假设我们需要2字节来存储一个字符，我们将需要30字节来存储一个平均查询。因此，我们将需要的总存储量是：
1亿 * 30字节 => 3GB我们可以预计这些数据每天都会有所增长，但我们也应该去掉一些不再被搜索的词汇。如果我们假设每天有2%的新查询，如果我们保持我们的索引持续一年，我们预期的总存储量是：
3GB + (0.02 * 3GB * 365天) => 25GB6. 数据分区
尽管我们的索引可以轻松地放在一台服务器上，但我们仍然可以对其进行分区，以满足我们对更高效率和更低延迟的需求。我们如何能有效地分区我们的数据，将其分布到多台服务器上呢？
a. 基于范围的分区：如果我们根据它们的首字母将我们的短语存储在不同的分区中怎么样？因此，我们将所有以字母"A"开头的词语保存在一个分区中，将以字母"B"开头的词语保存在另一个分区中，以此类推。我们甚至可以将某些出现频率较低的字母合并到一个数据库分区中。我们应该静态地提出这种分区方案，这样我们就可以以一种可预测的方式存储和搜索词语。
这种方法的主要问题在于，它可能导致服务器的负载不均衡，例如，如果我们决定将所有以字母"E"开头的词语放入一个数据库分区，但后来我们发现我们有太多以字母"E"开头的词语，无法放入一个数据库分区。
我们可以看到，以上问题会在每个静态定义的方案中发生。静态地计算我们的每个分区是否能适应一台服务器是不可能的。
b. 基于服务器最大容量的分区：假设我们根据服务器的最大内存容量对我们的Trie树进行分区。只要服务器有可用的内存，我们就可以继续在服务器上存储数据。每当一个子树无法装入一个服务器时，我们就在那里分割我们的分区，将该范围分配给这个服务器，并转移到下一个服务器重复这个过程。假设我们的第一台Trie服务器可以存储所有从"A"到"AABC"的词语，这意味着我们的下一台服务器将从"AABD"开始存储。如果我们的第二台服务器能存储到"BXA"，那么下一台服务器将从"BXB"开始，依此类推。我们可以保留一个哈希表，以快速访问这个分区方案：
服务器1, A-AABC 服务器2, AABD-BXA 服务器3, BXB-CDA
对于查询，如果用户输入了"A"，我们必须查询服务器1和2来找到最佳的建议。当用户输入了"AA"，我们仍然需要查询服务器1和2，但是当用户输入了"AAA"，我们只需要查询服务器1。
我们可以在我们的Trie服务器前面放一个负载均衡器，它可以存储这个映射并重定向流量。另外，如果我们正在从多个服务器查询，我们要么需要在服务器端合并结果来计算总的最佳结果，要么让我们的客户端这样做。如果我们更愿意在服务器端做这件事，我们需要在负载均衡器和Trie服务器之间引入另一层服务器（我们称之为汇总器）。这些服务器将汇总来自多个Trie服务器的结果，并返回最佳结果给客户端。
基于最大容量的分区仍然可能导致我们有热点，例如，如果有很多以"cap"开头的词语的查询，持有它的服务器将比其他服务器负载更高。
c. 基于词语的哈希进行分区：每个词语将被传递给一个哈希函数，该函数将生成一个服务器号，我们将在该服务器上存储词语。这将使我们的词语分布随机，从而最小化热点。要查找一个词语的联想建议，我们必须询问所有的服务器，然后汇总结果。
7. 缓存
我们应该意识到，缓存最常搜索的词语将对我们的服务非常有帮助。有一小部分查询将负责大部分的流量。我们可以在持有最常搜索的词语和它们的联想建议的Trie服务器前面有单独的缓存服务器。在请求Trie服务器之前，应用服务器应该检查这些缓存服务器，看看它们是否有所需的搜索词语。
我们还可以建立一个简单的机器学习(ML)模型，试图根据简单的计数、个性化或趋势数据等，预测每个建议的用户参与度，并缓存这些词语。
8. 复制和负载均衡器
我们应该为我们的Trie服务器做副本，既为了负载平衡，也为了容错。我们还需要一个负载均衡器，它能跟踪我们的数据分区方案，并根据前缀重定向流量。
9. 容错性
当一个Trie服务器宕机时会发生什么？如上文所述，我们可以有一个主从配置；如果主服务器宕机，从服务器可以在故障转移后接管。任何重新启动的服务器，都可以根据最后一次快照重建Trie树。
10. 联想输入客户端
我们可以在客户端进行以下优化，以提高用户体验：
1. 只有当用户50毫秒内没有按任何键时，客户端才应尝试连接服务器。
2. 如果用户持续不断地输入，客户端可以取消正在进行的请求。
3. 起初，客户端可以等待用户输入几个字符。
4. 客户端可以从服务器预先获取一些数据，以节省未来的请求。
5. 客户端可以在本地存储最近的建议历史。最近的历史有很高的复用率。
6. 与服务器建立早期连接被证明是最重要的因素之一。当用户打开搜索引擎网站时，客户端可以与服务器打开一个连接。所以当用户输入第一个字符时，客户端不会浪费时间去建立连接。
7. 为了提高效率，服务器可以将其缓存的一部分推送到内容分发网络(CDNs)和互联网服务提供商(ISPs)。
11. 个性化
用户会根据他们的历史搜索、位置、语言等，接收一些联想建议。我们可以在服务器上分别存储每个用户的个人历史，并在客户端进行缓存。服务器可以在将最终结果发送给用户之前，将这些个性化的词语添加到最终集合中。个性化的搜索应该总是排在其他搜索之前。
推荐阅读
你好，我是拾叁，7年开发老司机、互联网两年外企5年。怼得过阿三老美，也被PR comments搞崩溃过。这些年我打过工，创过业，接过私活，也混过upwork。赚过钱也亏过钱。一路过来，给我最深的感受就是不管学什么，一定要不断学习。只要你能坚持下来，就很容易实现弯道超车！所以，不要问我现在干什么是否来得及。如果你还没什么方向，可以先关注我，这里会经常分享一些前沿资讯和编程知识，帮你积累弯道超车的资本。